Computer systems have been used to recognize which characters of an alphabet correspond to handwritten data. Typically, recognition systems input handwriting using an electronic tablet and pen and then compare the handwriting to a database of character prototypes. For each character in the alphabet, the character prototypes for that character describe various ways in which that character may be handwritten. After comparing the handwriting to the character prototypes, the recognition system recognizes the handwriting as that character with the character prototype that most closely matches the handwriting. Generally, the accuracy of such recognition systems decreases and the time needed for recognition increases with the complexity of the alphabet to be recognized. The Chinese and Kanji alphabets, which have some 50,000 characters, are examples of such complex alphabets.
One handwriting recognition system that has been developed to recognize Kanji characters decomposes the handwritten characters into component strokes and categorizes each stroke by its characteristic features. The features by which a stroke is categorized are based on the shape and direction of the stroke (shape feature) and the starting and ending points of the stroke (position feature). A shape feature could be, for example, a horizontal stroke drawn from left to right or a slanted stroke drawn from the bottom to the top. Each shape feature is assigned a unique integer value. The recognition system identifies the shape feature and position feature of each stroke in a handwritten character and creates a shape feature string and a position feature string for that character. The feature strings are ordered based on the order in which the corresponding stroke was written. The feature in the first place of a feature string, for example, corresponds to the first written stroke of the character represented by the feature string. The shape and position feature strings contain a description of the handwritten character that is used to find a matching character prototype. For each character, the character prototypes contain the shape and position feature strings describing the various ways in which that character may be written.
If each character were always handwritten in the same unique way, then the recognition system would need only one character prototype for each character and recognition would be simplified. However, different people may write the same character by writing the strokes in different orders and in different relative positions, by substituting a stroke with one shape feature for a stroke of another shape feature, and by using different number of strokes. Thus, a particular character may have many character prototypes. Even with the use of many character prototypes, some handwritten characters may still not exactly match one of the character prototypes.
In order to recognize such unknown handwritten characters, the recognition system computes a matching score for every character prototype in the prototype database. The recognition system computes the matching score by comparing how closely the shape and position feature strings of the unknown character match the shape and position feature strings of a character prototype. The recognition system typically compares the feature string of the unknown character only to the feature strings of character prototypes with strings of the same length (i.e., same number of strokes) and only compares features at the same relative place within the feature strings.
The recognition system uses a shape feature matrix that is a square matrix whose row and columns are indexed by the shape features. Each entry of the matrix contains a rough estimate of the likelihood that the indexed pair of shape features can be substituted for one another. To determine how closely the shape feature strings of an unknown character and a character prototype match, the recognition system retrieves the first shape feature from each shape feature string and retrieves the matrix entry that is indexed by this pair of shape features. The recognition system then retrieves the second shape feature from each feature string and retrieves the matrix entry that is indexed by this pair of shape features. The recognition system then repeats this process for each pair of shape features in the shape feature strings. The recognition systems then totals all the retrieved entries. The higher the total, the more likely the unknown character matches the character prototype.
The recognition system uses the position features to make a threshold determination as to whether the unknown character and the character prototype match. For each pair of position features, the recognition system calculates the Euclidean distance between starting points of the strokes and the Euclidean distance between the ending points of the strokes. The recognition system then totals all the Euclidean distances. If the total distance exceeds a predefined threshold, then the character prototype is rejected as a possible matching character. Such a recognition system is described in U.S. patent application Ser. No. 08/452,660, which is hereby incorporated by reference.
The accuracy of the above described recognition system depends, in part, on the particular set of shape features that are defined, on the estimates in the shape feature matrix, and on the setting of the distance threshold. Thus, various combinations of different sets of shape features, different entries in the shape feature matrix, and different distance thresholds may improve accuracy. However, defining sets of shape features, estimating entries for the shape feature matrix, and setting the distance threshold can be very time-consuming. First, a person trying to improve the accuracy of the recognition system would define a new set of features. Then, the person would estimate entries for the shape feature matrix and set the distance threshold based on the newly defined set of shape features. Since there may be 20 shape features in a set, it may take a considerable amount of time for the person to generate the matrix of estimates. The person would then test the accuracy of the recognition system by regenerating the database of character prototypes and then attempting to recognize a large sample of handwritten characters. If the accuracy is not acceptable, then the estimates and distance threshold would need to be refined and the accuracy re-tested by again attempting to recognize a large sample of handwritten characters. This re-estimating and re-testing is very time consuming. Moreover, it is even more time consuming when the set of shape features is redefined. It is also not clear how to weigh the results of the shape feature comparison and the feature distances or whether either or both of the results can be linearly scaled to give matching values that might roughly correspond to statistical probabilities. In short, the accuracy of the recognition system depends on a fortuitous choice of a set of shape features, tedious trial and error refinements of the estimates in the shape feature matrix and the distance threshold, and a somewhat arbitrary choice of how to weigh the results of the shape feature comparison with the distance threshold.